package 队列;

import com.alibaba.fastjson.JSON;
import 栈.TreeNode;

import java.util.*;

public class No103二叉树的锯齿形层次遍历 {

    /**
     * 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
     *
     * 例如：
     * 给定二叉树 [3,9,20,null,null,15,7],
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回锯齿形层次遍历如下：
     * [
     *   [3],
     *   [20,9],
     *   [15,7]
     * ]
     */

    //通过队列,广度优先遍历
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        if(root==null)
            return new ArrayList<>();

        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        List<List<Integer>> lists=new ArrayList<>();
        boolean flag=true;
        while (!queue.isEmpty()){
            int count=queue.size();
            List<Integer> list=new ArrayList<>();
            while (count>0){
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if(poll.left!=null)
                    queue.add(poll.left);
                if(poll.right!=null)
                    queue.add(poll.right);
                count--;
            }
            if(!flag)
                Collections.reverse(list);
            lists.add(list);
            flag=!flag;
        }

        return lists;
    }

    //通过递归,深度优先
    public static List<List<Integer>> zigzagLevelOrder2(TreeNode root){

        List<List<Integer>> list=new ArrayList<>();

        dg(list,0,root);

        return list;

    }

    private static void dg(List<List<Integer>> lists,int level,TreeNode node){

        if(node==null)
            return;

        if(lists.size()<level+1){
            //没有此队列,就新增一个
            lists.add(new ArrayList<>());
        }
        if(level%2==0)
            lists.get(level).add(node.val);//正着来
        else
            lists.get(level).add(0,node.val);//反着来

        if (node.right != null)
            dg(lists, level + 1, node.right);
        if (node.left != null)
            dg(lists, level + 1, node.left);
    }

    public static void main(String[] args) {
        TreeNode node = TreeNode.getNode();
        System.out.println(JSON.toJSONString(zigzagLevelOrder2(node)));
    }

}
